package com.berchen.算法.KMP算法;

import java.util.Arrays;

/**
 * KMP算法
 * 移动的位数=已匹配字符串长度-该字符串的部分匹配值。
 * 如何计算部分匹配值：
 *  a 部分匹配值 0
 *  ab 前缀 a 后缀 b  前缀和后缀相同的为0 个  所以部分匹配值为0
 *  aa 前缀 a 后缀 a  前缀和后缀相同的为1 个  所以部分匹配值为1
 *  aba 前缀  a ab 后缀 a ba  前缀和后缀相同的为 1 个 所以部分匹配值为1
 */
public class KMPAlgorithm {

    public static void main(String[] args) {

        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int next[] = kmpNext(str2);
        System.out.println(Arrays.toString(next));
        int index = kmpSearch(str1, str2, next);
        System.out.println(index);
    }

    /**
     * 通过KMP算法 得到子串第一次在源字符串中出现的索引
     *
     * @param str1 源字符串
     * @param str2 子字符串
     * @param next 子字符串的部分匹配值
     * @return
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        // i 从0 开始  ，j 从0 开始
        for (int i = 0, j = 0; i < str1.length(); i++) {
            // KMP算法的核心点 记住！！！！！！！！！！
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            //
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            // str2 字符串长度等于 j的长度  说明str2已经匹配完了  就可以返回了
            if (j == str2.length()) {
                return i - j + 1;    // i j  都是从0 开始  j= 3 i= 2
            }
        }
        return -1;
    }

    /**
     * 获取一个字符串子串的部分匹配值表
     *
     * @param dest
     * @return
     */
    public static int[] kmpNext(String dest) {

        int[] next = new int[dest.length()];
        next[0] = 0;  // 一个字符的部分匹配值为0
        // i 从 1 开始   ，j 从 0 开始
        for (int i = 1, j = 0; i < dest.length(); i++) {

            // dest.charAt(i)!=dest.charAt(j) 满足时  我们需要从next[j-1]中获取新的j
            // 这是KMP算法的核心 记住！！！！！！
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            //dest.charAt(i)==dest.charAt(j) 满足时 部分匹配值+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
